//
//  Problem1043.swift
//  TestProject
//
//  Created by 毕武侠 on 2021/2/25.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 1043. 分隔数组以得到最大和
 给你一个整数数组 arr，请你将该数组分隔为长度最多为 k 的一些（连续）子数组。分隔完成后，每个子数组的中的所有值都会变为该子数组中的最大值。
 返回将数组分隔变换后能够得到的元素最大和。
 注意，原数组和分隔后的数组对应顺序应当一致，也就是说，你只能选择分隔数组的位置而不能调整数组中的顺序。

 示例 1：
     输入：arr = [1,15,7,9,2,5,10], k = 3
     输出：84
     解释：
     因为 k=3 可以分隔成 [1,15,7] [9] [2,5,10]，结果为 [15,15,15,9,10,10,10]，和为 84，是该数组所有分隔变换后元素总和最大的。
     若是分隔成 [1] [15,7,9] [2,5,10]，结果就是 [1, 15, 15, 15, 10, 10, 10] 但这种分隔方式的元素总和（76）小于上一种。
 示例 2：
     输入：arr = [1,4,1,5,7,3,6,1,9,9,3], k = 4
     输出：83
 示例 3：
     输入：arr = [1], k = 1
     输出：1
 提示：
     1 <= arr.length <= 500
     0 <= arr[i] <= 109
     1 <= k <= arr.length
 */
@objcMembers class Problem1043: NSObject {
    func solution() {
        print(maxSumAfterPartitioning1([1,15,7,9,2,5,10], 3))
        // 472891870
        print(maxSumAfterPartitioning1([60803,944497,997590,498033,150561,138570,153226,41113,622181,822694,800277,115626,645658,137059,928394,297438,231177,163449,769246,808442,604124,957600,332557,636426,324832,34085,58274,792852,74280,577167,786935,548388,378009,468173,194692,4264,787409,636893,627810,300623,865415,422759,32705,784116,248487,692081,13592,221155,193259,873781,602722,46711,942154,103237,174444,199004,62018,923809,468472,722938,491426,399914,21857,590369,621475,168235,250082,46937,5906,502955,534299,431492,942630,135032,811501,837998,102081,460524,676687,466534,89827,449525,939156,587723,71590,352189,227615,288550,419637,30495,952893,338146,774358,387564,601329,364223,257403,596289,153399,55681,470354,862,949899,731125,841859,745065,525773,559083,735346,241801,241180,284880,674538,150263,677914,286711,601216,71972,73814,308568,891030,818763,800424,419668,193045,750926,559606,898789,586095,930839,363845,980937,847964,967309,997019,755524,635262,130212,244089,257841,734340,823241,193343,939491,178081,43222,427239,917935,523402,418021,552442,296397,419581,643778,776934,197956,718196,952343,81731,753742,659718,215425,977866,618482,31016,58178,193463,441685,959938,377448,567921,986154,625899,738764,568902,57288,102415,829033,554103,377734,676018,31829,122714,44179,983333,544640,667643,943597,852364,521890,195216,504393,140546,868847,234415,164537,732718,473529,857517,109696,445229,197802,761298,958227,128788,898174,707361,947575,202226,256555,773458,96661,115609,342002,319858,45818,397502,261035,908705,552689,557707,430877,114334,567609,853348,491914,67140,208166,248408,304553,112882,884566,391070,332134,391223,295138,725871,223549,580189,457880,300041,967768,429507,14898,278694,807136,27635,773323,312812,459550,57864,201279,298593,890103,249608,984192,243860,81484,46107,75286,144687,87170,703517,209153,478809,479499,76676,588039,738685,193201,900227,740220,551924,125356,451879,725830,38239,684378,633482,288467,477407,170704,597311,812008,80234,573377,491131,704720,618000,719345,509774,865570,537086,199030,158822,958648,772049,404505,210034,424631,582812,137808,573763,685885,473681,672950,736963,980119,509251,569263,18742,787980,159483,534712,591557,377422,880540,935183,521554,122914,801318,230512,304088,411977,822265,455697,982932,275244,465469,759159,437495,884595,590057,723689,99534,865253,896394,410733,849464,210890,314197,319102,181533,865572,303187,720239,747068,625386,678426,276119,505310,931837,479139,69758,609141,723480,149875,900623,697820,252853,261136,488812,211991,298084,58280,184791,314646,34493,123669,806843,617544,873614,258784,544966,731973,408230,293348,410096,391386,758737,887376,172639,170871,608845,72635,395790,135838,259691,10201,298607,101346,684605,312572,569216,349621,750058,328019,996465,343470,197823,159462,65254,121333,370719,678387,887305,986753,75000,839543,433748,782969,100162,252730,746210,918444,882351,35685,467866,616596,199017,64972,978495,804996,128669,28708,609848,419344,904041,736143,685558,666976,644487,724103,986879,359785,499187,508293,110529,417018,644699,19174,812057,551974,334155,166744,319461,395756,983381,41131,888565,794038,702043,462463,607891,782513,66009,62717,926726,297383,86362,32332,366899,42931,11379,997700,970639,188890,328733,623300,4761,498125,741551,960140,428292], 311))
    }
    
    /*
     动态规划 超时
     1: 创建一个二维数组: dp[len][len]
     2: dp[i][j]： i～j的最大和
     3: dp[i][j] = max()
        依次求出最大值：
        dp[i][i]   + dp[i+1][j]
        dp[i][i+1] + dp[i+2][j]
        dp[i][i+2] + dp[i+3][j]
     => for k in(0...k)
            dp[i][i+k] + dp[i+k+1][j]
     */
    func maxSumAfterPartitioning(_ arr: [Int], _ k: Int) -> Int {
        if arr.count == 1 {
            return arr[0]
        }
        if k == 1 {
            return arr.reduce(0) { (first, second) -> Int in
                return first + second
            }
        }
        
        var dp = Array(repeating: Array(repeating: -1, count: arr.count), count: arr.count)
        // 斜着遍历
        for i in 0..<arr.count {
            for j in i..<arr.count {
                let ii = j-i
                if ii == j {                // 特例：一个数时，最大值就是自身
                    dp[ii][j] = arr[ii]
                } else if j == ii + 1 {     // 特例：2个数时，最大值就是 max * 2
                    dp[ii][j] = max(arr[ii], arr[ii+1]) * 2
                } else {
                    // dp[ii][j]: ii~j的最大值：依次求出最大值： 计算过多，超时
                    // dp[ii][ii+0] + dp[ii+1][j]
                    // dp[ii][ii+1] + dp[ii+2][j]
                    // dp[ii][ii+2] + dp[ii+3][j]
                    let n = min(j-ii+1, k)
                    var maxValue = -1
                    for t in 0..<n {
                        if ii+t+1 > j {
                            maxValue = max(maxValue, getReduceArray(arr, ii, ii+t))
                        } else {
                            maxValue = max(maxValue, dp[ii][ii+t] + dp[ii+t+1][j])
                        }
                    }
                    dp[ii][j] = maxValue
                }
            }
        }
        return dp[0][arr.count-1]
    }
    
    func getReduceArray(_ arr: [Int], _ i: Int, _ j: Int) -> Int {
        var maxValue = 0
        for t in i...j {
            maxValue = max(arr[t], maxValue)
        }
        return maxValue * (j - i + 1)
    }
    
    /*
     动态规划
     1: 创建一个一维数组 dp[len]
     2: dp[i]: 0～i最大值
     3: dp[i] = max
        dp[i]
        dp[i-1] + max(arr[i]) * 1
        dp[i-2] + max(arr[i-1], arr[i-2]) * 2
        dp[i-3] + max(arr[i-1], arr[i-2], arr[i-3]) * 3
     */
    func maxSumAfterPartitioning1(_ arr: [Int], _ k: Int) -> Int {
        if arr.count == 1 {
            return arr[0]
        }
        if k == 1 {
            return arr.reduce(0) { (first, second) -> Int in
                return first + second
            }
        }
        
        var dp = Array(repeating: 0, count: arr.count)
        dp[0] = arr[0]
        for i in 1..<dp.count {
            var maxValue = 0
            let n = min(k, i+1)
            for j in 0..<n {
                maxValue = max(maxValue, arr[i-j])
                if j == i {       //
                    dp[i] = max(dp[i], maxValue * (j+1))
                } else {
                    dp[i] = max(dp[i], dp[i-j-1] + maxValue * (j+1))
                }
                
            }
        }
        return dp.last ?? 0
    }
}
